namespace ds
{
    /**
     * 线段树
     * 
     * 用于高效运算指定区间 [a, b] 的 operation 运算
     * 
     * @see https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/tree/segment-tree/SegmentTree.js
     * @see [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree)
     * @see [YouTube](https://www.youtube.com/watch?v=ZBHKZF5w4YU&index=65&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
     * @see [GeeksForGeeks](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)
     */
    export class SegmentTree
    {
        /**
         * 输入数组
         */
        inputArray: number[];
        /**
         * 线段树数组
         */
        segmentTree: number[];

        /**
         * 运算无效值
         * 
         * 对任意的 x 都满足 x == operation( x, operationFallback)
         * 
         * 例如 Infinity 是 min(a,b) 的 运算无效值， 0 是 add(a,b) 的运算无效值。
         */
        operationFallback: number;

        /**
         * 操作函数
         */
        operation: (a: number, b: number) => number;

        /**
         * 构建线段树
         * 
         * @param inputArray 输入数组
         * @param operation 操作函数 parent = operation(leftChild,rightChild)
         * @param operationFallback 运算无效值，对任意的 x 都满足 x == operation( x, operationFallback)
         */
        constructor(inputArray: number[], operation: (a: number, b: number) => number, operationFallback: number)
        {
            this.inputArray = inputArray;
            this.operation = operation;
            this.operationFallback = operationFallback;

            this.segmentTree = this.initSegmentTree(this.inputArray);

            this.buildSegmentTree();
        }

        /**
         * 初始化线段树
         * 
         * @param inputArray 输入数组
         */
        initSegmentTree(inputArray: number[])
        {
            let segmentTreeArrayLength: number;
            const inputArrayLength = inputArray.length;

            if (isPowerOfTwo(inputArrayLength))
            {
                // 如果原始数组长度是2的幂。
                segmentTreeArrayLength = (2 * inputArrayLength) - 1;
            } else
            {
                //如果原始数组的长度不是2的幂，那么我们需要找到下一个2的幂并使用它来计算树数组的大小。这是因为我们需要用null填充完美二叉树中的空子树。这些零需要额外的空间。
                const currentPower = Math.floor(Math.log2(inputArrayLength));
                const nextPower = currentPower + 1;
                const nextPowerOfTwoNumber = 2 ** nextPower;
                segmentTreeArrayLength = (2 * nextPowerOfTwoNumber) - 1;
            }

            return new Array(segmentTreeArrayLength).fill(null);
        }

        /**
         * 构建线段树
         */
        buildSegmentTree()
        {
            const leftIndex = 0;
            const rightIndex = this.inputArray.length - 1;
            const position = 0;
            this.buildTreeRecursively(leftIndex, rightIndex, position);
        }

        /**
         * 构建线段树递归
         * 
         * @param leftInputIndex 左输入索引
         * @param rightInputIndex 右输入索引
         * @param position 位置
         */
        buildTreeRecursively(leftInputIndex: number, rightInputIndex: number, position: number)
        {
            // 如果左输入索引和右输入索引相等那就意味着我们已经完成了分裂，我们已经到了片段树的叶结点。我们需要将这个叶值从inputarray复制到段树。
            if (leftInputIndex === rightInputIndex)
            {
                this.segmentTree[position] = this.inputArray[leftInputIndex];
                return;
            }

            // 将输入数组分成两半，并递归地处理它们。
            const middleIndex = Math.floor((leftInputIndex + rightInputIndex) / 2);
            // 处理输入数组的左半边。
            this.buildTreeRecursively(leftInputIndex, middleIndex, this.getLeftChildIndex(position));
            // 处理输入数组的右半边。
            this.buildTreeRecursively(middleIndex + 1, rightInputIndex, this.getRightChildIndex(position));

            //一旦每个树叶不是空的，我们就可以使用提供的操作函数自底向上构建树。
            this.segmentTree[position] = this.operation(
                this.segmentTree[this.getLeftChildIndex(position)],
                this.segmentTree[this.getRightChildIndex(position)],
            );
        }

        /**
         * 范围查询
         * 
         * @param queryLeftIndex 查询左索引
         * @param queryRightIndex 查询右索引
         */
        rangeQuery(queryLeftIndex: number, queryRightIndex: number)
        {
            const leftIndex = 0;
            const rightIndex = this.inputArray.length - 1;
            const position = 0;

            return this.rangeQueryRecursive(
                queryLeftIndex,
                queryRightIndex,
                leftIndex,
                rightIndex,
                position,
            );
        }

        /**
         * 范围查询递归求值
         * 
         * @param queryLeftIndex 查询左索引
         * @param queryRightIndex 查询右索引
         * @param leftIndex 输入数组段的左索引
         * @param rightIndex 输入数组段的右索引
         * @param position 二叉树的根位置
         */
        rangeQueryRecursive(queryLeftIndex: number, queryRightIndex: number, leftIndex: number, rightIndex: number, position: number): number
        {
            if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex)
            {
                // 全部重叠
                return this.segmentTree[position];
            }

            if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex)
            {
                // 没有重叠，返回一个 运算无效值
                return this.operationFallback;
            }

            // 部分重叠
            const middleIndex = Math.floor((leftIndex + rightIndex) / 2);

            const leftOperationResult = this.rangeQueryRecursive(
                queryLeftIndex,
                queryRightIndex,
                leftIndex,
                middleIndex,
                this.getLeftChildIndex(position),
            );

            const rightOperationResult = this.rangeQueryRecursive(
                queryLeftIndex,
                queryRightIndex,
                middleIndex + 1,
                rightIndex,
                this.getRightChildIndex(position),
            );

            return this.operation(leftOperationResult, rightOperationResult);
        }

        /**
         * 获取左子结点索引
         * 
         * @param parentIndex 父结点索引
         */
        getLeftChildIndex(parentIndex: number)
        {
            return (2 * parentIndex) + 1;
        }

        /**
         * 获取右子结点索引
         * 
         * @param parentIndex 父结点索引
         */
        getRightChildIndex(parentIndex: number)
        {
            return (2 * parentIndex) + 2;
        }
    }

}